package offer.nowcoder.queue_stack;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author DengYuan2
 * @create 2021-02-18 20:28
 */
public class n_41_2 {
    public static void main(String[] args) {
        n_41_2 n = new n_41_2();
        n.Insert2('g');
        System.out.println(n.FirstAppearingOnce2());
        n.Insert2('o');
        System.out.println(n.FirstAppearingOnce2());
        n.Insert2('o');
        System.out.println(n.FirstAppearingOnce2());
        n.Insert2('g');
        System.out.println(n.FirstAppearingOnce2());
        n.Insert2('l');
        System.out.println(n.FirstAppearingOnce2());
        n.Insert2('e');
        System.out.println(n.FirstAppearingOnce2());
    }

    List<Character> charList = new ArrayList<Character>();
    List<Integer> countList = new ArrayList<Integer>();

    /**
     * 我的写法-思路-一个存放插入的字符，一个存放相应字符的出现个数
     *
     * @param ch
     */
    public void Insert(char ch) {
        int index = charList.indexOf(ch);
        if (index == -1) {
            charList.add(ch);
            countList.add(1);
        } else {
            countList.set(index, countList.get(index) + 1);
        }
    }

    public char FirstAppearingOnce() {
        for (int i = 0; i < countList.size(); i++) {
            if (countList.get(i) == 1) {
                return charList.get(i);
            }
        }
        return '#';
    }

    /**
     * 大神的写法-思路：
     * 使用统计数组来统计每个字符出现的次数，本题涉及到的字符为都为 ASCII 码，
     * 因此使用一个大小为 128 的整型数组就能完成次数统计任务。
     * 使用队列来存储到达的字符，并在每次有新的字符从字符流到达时移除队列头部
     * 那些出现次数不再是一次的元素。因为队列是先进先出顺序，因此队列头部的元
     * 素为第一次只出现一次的字符。
     *
     * @param ch
     */
    int[] cnts = new int[128];
    Queue<Character> queue = new LinkedList<>();

    public void Insert2(char ch) {
        cnts[ch]++;
        queue.add(ch);
        while (!queue.isEmpty() && cnts[queue.peek()] != 1) {
            queue.poll();
        }


    }

    public char FirstAppearingOnce2() {
        if (queue.isEmpty()){
            return '#';
        }
        return queue.peek();
    }


}
